The present invention relates to a method, system, and apparatus for automatically designing a logic circuit, particularly a multiplier or a logic circuit including a multiplier, and to a multiplier.
Conventional multipliers for performing multiplication with digital information are often used not only as single, independent LSIs but also as elements to be mounted in such LSIs as DSP (digital signal processor). However, as the bit width is increased in multiplication and their applications are more diversified, multipliers of this type are required to have reduced circuit size and chip area as well as to operate at higher speed. To meet the requirements, circuit systems using various multiplication methods have been proposed.
For example, a multiplication method using the Booth's 2-bit recode system, which is one of the highest-speed multiplication methods, is disclosed in "Nikkei Electronics" (May 29, pp.76-89(1978)). The multiplication method uses the following algorithm in order to increase the speed of multiplication.
If an n-bit multiplicand X is to be multiplied by an m-bit multiplier factor Y, e.g., the multiplier factor Y is represented by two's complements as follows: ##EQU1## where ym=ys, q=m/2 if m is an even number or q=(m-1)/2 if m is an odd number, and y0=0 (y is a value given for convenience).
Hence, the product P of X and Y becomes ##EQU2##
Here, since the values of y.sub.2i, y.sub.2i+1, and y.sub.2i+2 are 0 or 1, (y.sub.2i +y.sub.2i+1 -2y.sub.2i+2) becomes 0, .+-.1, or .+-.2, so that each of their partial products becomes a value obtained by multiplying 0, .+-.X, or .+-.2X by 2.sup.2i.
TABLE 1 ______________________________________ y.sub.2i+2 y.sub.2i+1 y.sub.2i (y.sub.2i + y.sub.2i+1 - 2y.sub.2i+2) ______________________________________ 0 0 0 0 0 0 1 +1 0 1 0 +1 0 1 1 +2 1 0 0 -2 1 0 1 -1 1 1 0 -1 1 1 1 0 ______________________________________
Here, a circuit for generating the partial products can be composed of a shifter primarily for shifting the multiplicand .+-.X by one bit till it is doubled and a shifter for shifting a mantissa (0, .+-.X or .+-.2X) by two bits till it is raised to the power of 2.sup.2i (weighing).
As for the number of logic stages in a circuit for calculating the total sum of the partial products, since the number of the partial products becomes q=m/2 (m is an even number) or q=(m-1)/2 (m is an odd number), it becomes approximately log.sub.2 m-1 (m is an even number) or log.sub.2 (m-1)-1 (m is an odd number) when a 2-input adder is connected so as to form a binary tree.
As an example of high-speed multipliers not using the Booth's 2-bit recode system, Japanese Patent Publication no. 03-017737 discloses a multiplier using redundant binary code.
With the multiplier mentioned above, when the multiplier factor is composed of 24 bits, the number of its partial products becomes 12 and the number of its logic stages becomes 4.
On the other hand, the increase in multiplication speed and the decrease in circuit size have been pursued not only by improving the performance of such a multiplication algorithm as mentioned above, but also by optimizing the circuit on the level of logic elements.
In recent years, multipliers and logic circuits containing multipliers are mostly designed by using automatic designing systems. Such a system is intended to eliminate a redundant portion of the circuit or to perform other operations by replacing a part of the circuit with an equivalent circuit having a smaller number of logic elements and logic stages in the case of, e.g., expanding circuit information on the level of logic elements to circuit information on the level of mounted elements, which are actually mounted in a chip.
If functional description information, which represents a function requested on the circuit in a hardware description language or the like, is inputted to such an automatic designing system, the system converts it to functional circuit information in an internal representation form, which represents a circuit composed of virtual functional elements whose functions are primarily and solely defined. Then, the resulting functional circuit information is further converted to logic circuit information which represents a circuit composed of real logic circuits, followed by the generation of mounted circuit information which represents a circuit to which real elements, mounted by specified technology, are allotted.
In the case where the function represented by the above functional description information includes multiplication, if a versatile multiplier having a specified bit width (e.g., 4, 8, 17, or 32 bits) has previously been in a library as a hardware macro and hence is available, for example, the versatile multiplier is allotted to the logic circuit. If a multiplier which is not in the library is required, a logic circuit constituting a shift-and-add multiplier or the like is newly generated. If either of the multiplier factor or multiplicand is a constant and the value thereof is a certain power-of-2 number, a circuit using a shifter is normally generated.
If the multiplier factor is a constant the value of which is not a power-of-2 number, however, the values of all the bits of a partial product that corresponds to a bit having the value of 0 in the multiplier factor become 0, so that signals from a circuit for generating or adding up such partial products disadvantageously remain in the same state.
To solve the problem, conventional automatic designing apparatus have adopted a method in which a multiplying circuit using variables as its multiplier factor and multiplicand and a circuit for generating a constant are generated before the circuit is optimized on the level of logic elements as mentioned above, thereby accomplishing the deletion of logic elements which generate signals remaining in the same state.
With the conventional automatic designing systems, however, the optimization of the circuit on the level of logic elements is localized, for the replacement by an equivalent circuit having a smaller number of logic elements and logic stages is limited to portions of the circuit that coincide with specific patterns which were preliminarily set. If such optimization is performed in the case where the multiplier factor or multiplicand is a constant, a circuit having the minimum number of logic elements and the like cannot necessarily be obtained. In particular, when carry-save adders are connected in a tree structure so as to add up partial products, the resulting tree is normally ill-balanced if the portion associated with a circuit for adding up the partial products in which the values of all the bits are 0 is omitted. Therefore, it is difficult to minimize the number of logic elements and the number of logic stages by partially replacing the circuit. Moreover, the conventional automatic designing apparatus were designed without any consideration of increasing the number of particular products in which the values of all the bits are 0.